#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct Node
{
    int x;
    int y;
    Node(int a, int b) :x(a),y(b){}
};

//LeetCode 994  Rotting Oranges
int orangesRotting(vector<vector<int>>& grid) {
    int countOne = 0;
    int countTwo = 0;
    int count = 0;
    int ifRotting = 0;
    queue<Node> q;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid[i].size();j++)
        {
            if(grid[i][j] == 1)
                countOne++;
            if(grid[i][j] == 2)
            {
                countTwo++;
                q.push(Node(i, j));
            }    
        }
    }
    if(countOne==0)
        return 0;
    if(countTwo==0)
        return -1;
    while(q.size())
    {
        int size = q.size();
        //进行一次感染
        for(int i=0;i<size;i++)
        {
            Node node = q.front();
            if(node.x-1>=0)
            {
                if(grid[node.x-1][node.y]==1)
                {
                    grid[node.x-1][node.y] = 2;
                    q.push(Node(node.x-1, node.y));
                    countOne--;
                    ifRotting++;
                }
            }
            if(node.x+1<grid.size())
            {
                if(grid[node.x+1][node.y]==1)
                {
                    grid[node.x+1][node.y] = 2;
                    q.push(Node(node.x+1, node.y));
                    countOne--;
                    ifRotting++;
                }
            }
            if(node.y-1>=0)
            {
                if(grid[node.x][node.y-1]==1)
                {
                    grid[node.x][node.y-1] = 2;
                    q.push(Node(node.x, node.y-1));
                    countOne--;
                    ifRotting++;
                }
            }
            if(node.y+1<grid[0].size())
            {
                if(grid[node.x][node.y+1]==1)
                {
                    grid[node.x][node.y+1] = 2;
                    q.push(Node(node.x, node.y+1));
                    countOne--;
                    ifRotting++;
                }
            }
            q.pop();
        }
        if(ifRotting>0)
        {
            count++;
            ifRotting = 0;
        }
    }
    if(countOne==0)
        return count;
    else
        return -1;
}
int main()
{
    vector<vector<int>> grid = {{2,1,1},{1,1,1},{0,1,2}};
    cout << orangesRotting(grid) << endl;
    return 0;
}